package algorithm.backtracing;

import java.util.*;

/**
 * LeetCode : https://leetcode.com/problems/permutations-ii/
 * Difficulty : Medium
 *
 * 给一个可能有重复数字的集合，找出数字所有唯一组合的集合。
 * Example:
 * Input: [1,1,2]
 * Output:
 * [
 *  [1,1,2],
 *  [1,2,1],
 *  [2,1,1]
 * ]
 * Created by yzy on 2019-09-02 15:38
 */
public class PermutationsII {

    public static void main(String[] args) {
        int[] arr = new int[]{2,2,1,1};
        System.out.println(permuteUnique(arr));
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null){
            return res;
        }



        List<List<Integer>> tmpList = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        tmp.add(nums[0]);
        tmpList.add(tmp);
        backtracking_BFS(res, tmpList, nums, 1);
        return res;
    }


    /**
     * RunTime: 59ms, 11.70%
     * Memory: 40.1MB, 44.78%
     * 使用Set来去重。效率有点慢
     *
     * @param list
     * @param tmp
     * @param nums
     * @param idx
     */
    private static void backtracking_BFS(List<List<Integer>> list, List<List<Integer>> tmp, int[] nums, int idx){
        if(idx == nums.length){
            Set<String> set = new HashSet<>();
            tmp.stream().forEach(subList -> {
                Optional<String> str = subList.stream().map(String::valueOf).reduce((a, b) -> a+b);
                if(set.add(str.get())){
                    list.add(subList);
                }
            });
            return;
        }else{
            Integer num = nums[idx];
            List<List<Integer>> newTmp = new ArrayList<>();
            for(List<Integer> subList : tmp){
                for(int i=0; i<=subList.size(); i++){
                    if(i<subList.size() && num==subList.get(i)){
                        continue;
                    }
                    List<Integer> innerList = new ArrayList<>(subList);
                    innerList.add(i,num);
                    newTmp.add(innerList);
                }
            }
            backtracking_BFS(list, newTmp, nums, idx+1);
        }
    }


    /**
     * 在Discuss看到的快速的解题思路
     * 参考：https://leetcode.com/problems/permutations-ii/discuss/370381/Java-or-1ms-or-Short-solution
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique_fast(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
        if(tempList.size() == nums.length){
            list.add(new ArrayList<>(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){
                if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
                used[i] = true;
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, used);
                used[i] = false;
                tempList.remove(tempList.size() - 1);
            }
        }
    }

}
